1. Overview

In this notebook we will use clustering to transform a sample image to see how clustering can be used beyond simple data frames.

2. Libraries

A new library will be installed and used - imager

library(imager)
package 㤼㸱imager㤼㸲 was built under R version 3.5.1Loading required package: magrittr

Attaching package: 㤼㸱imager㤼㸲

The following object is masked from 㤼㸱package:magrittr㤼㸲:

    add

The following objects are masked from 㤼㸱package:stats㤼㸲:

    convolve, spectrum

The following object is masked from 㤼㸱package:graphics㤼㸲:

    frame

The following object is masked from 㤼㸱package:base㤼㸲:

    save.image

3. Loading sample image

This function will load a sample image from a file or URL using imager library and store it as CIMG file (Effectively being a very large string of numbers).

Display function will show you the picture in the separate window

More information can be found under: https://cran.r-project.org/web/packages/imager/vignettes/gettingstarted.html

image <-load.image("FRABEL.jpg")
display(image)

4. Reformatting an image

Here we will transform the data from an image to a dataframe so it can be read as a bunch of RGB (red, green, blue) values for a single pixel. THis is actually how a computer stores an image.

dfimage <- as.data.frame(image)
head(dfimage)

x - width
y - height
cc - depth
value - colour channel

The function below reshape (transforms) the data frame onto a pivot table that will show RGB values for each pixel and turns into a “wide” picture

pivotimage <- reshape(dfimage, direction = "wide", timevar = "cc", idvar = c("x", "y"))
head(pivotimage)

After reshaping - we need to rename columns as per the RGB convention (as these values relate to the density of each colour in the colour mix)

names(pivotimage)[3] <- "R"
names(pivotimage)[4] <- "G"
names(pivotimage)[5] <- "B"
head(pivotimage)

5. Sneak peek onto the image

The easiest way to see the image is to use ggplot function and draw it as a plot. For this we need to use ggplot2 library

However, first we need to convert data from RGB to HEX to allow computer to understand what colour to use. For this, we will use “rgb” function and store it as a separate value under imgcolour variable.

imgcolour <- rgb(pivotimage[c("R","G","B")])

Now we can plot the image using ggplot function

library(ggplot2)
package 㤼㸱ggplot2㤼㸲 was built under R version 3.5.1
ggplot(data=pivotimage)+
  aes(x=x, y=-y)+
  geom_point(colour=imgcolour)+
  coord_fixed()

ggplot function allows you to do many things, but you need to specify every parameter (as oppose to qplot function for example). Remember to use “+” sign to add another parameter
data = dataframe - in this case reshaped one (pivotimage)
aes allows to specify aesthetics and dimensions. In this case it’s easy (x and y), but you need to be vary that you need to reverse y value (-y)
geom allows to define the shae of the graph and add parameters to this shape. In our case geom_point is best suited as it plots dots with colors defined in “colour” parameter. Colour should equal newly created HEX values so that the program will know what HEX value each pixel should have.
coord_fixed parameter allows to fix the ratio for both axis - otherwise the picture could look too wide or too narrow.

6. Working with k-means - clustering

Here we are going to create clusters for our image using k-means algorithm and function.

First we need to define the number of clusters that we want to have - let’s choose 3 and store it under a new variable

kparameter <- 4

Then we need to define imgCluster variable that will store all rows from the pivot table but only RGB columns

imgCluster <- data.frame(pivotimage$R, pivotimage$G, pivotimage$B)
head(imgCluster)

Now we’re going to use k-means to find centroids for us. These are shown below and represents most important colours on the image

kmeansresults <- kmeans(imgCluster, centers = kparameter)
kmeansresults$centers
  pivotimage.R pivotimage.G pivotimage.B
1    0.4456714    0.5201895    0.2536242
2    0.6946025    0.7333159    0.7122830
3    0.1641468    0.1501433    0.1441674
4    0.8261590    0.2229151    0.1736795

K-means also created clusters for each pixel so we can group pixels together. Now adding newly created groups to each pixel

pivotimage$Cluster <- kmeansresults$cluster

7. Cluster visualisation

This is how you can visualize the results of the clustering. To do that we will use some functions from “plotly” library so you’d need to install it first.

First we need to convert centroids found from RGB onto HEX using rgb function.

ClusterColours <- rgb(kmeansresults$centers)
ClusterColours
[1] "#728541" "#B1BBB6" "#2A2625" "#D3392C"

Now we have got colours of these centroids and we can use plot function to view them. This code block will plot rectangular boxes in each color (centroid) with a name of the cluster in it.

SetTextContrastColor <- function(color)
{
  ifelse( mean(col2rgb(color)) > 127, "black", "white")}
##Function above will allow you to define whether to set the color of the cluster name in white or black depending on the cluster colour (if dark then white label and vice versa)
plot(0, type = "n", axes = FALSE, ylab = "", xlab = "", ylim = c(2,0), xlim = c(0,5))
title("Clusters as colours")
##Plotting a space without data (0), type n, axes not visible and with size 5 in width and size 2 height
for (i in 0:(kparameter-1)) {
  rect(i,0,i+1,1,col=ClusterColours[i+1])
  text(i+0.5,0.5, i+1, col=SetTextContrastColor(ClusterColours[i+1]))}

##This loop function will plot rectangulars in colors of clusters and labels on the previously created space. 

Now we’re adding cluster group to each point in the imgCluster frame based on centroids found using k-means

imgCluster$cluster <-kmeansresults$cluster
head(imgCluster)

Now we’re ready to plot some more ..

library(plotly)
imgPivotSample <- pivotimage[sample(1:nrow(pivotimage), 1000, replace=FALSE),]
##Creating a sample of points from the image (processing of the full image might crash computer as it has millions of pixels)
plot <- plot_ly(
    imgPivotSample, x = ~R, y = ~G, z = ~B,
##Take sample of 1000 points and for each point - imgPivotSample
## For each dimension x,y,z assign one colour (R,G,B) so RGB would be coordinates on the 3D plot
    color = ~Cluster, 
## Color parameter takes the value from the cluster column for each point and plot this point in a colour of the cluster 
    colors = rgb(kmeansresults$centers),
## colors parameter shows a vector of colours in HEX format (after converting centroids using rgb function)
    marker = list(symbol = "circle", size = 4)
## marker parameter sets point type and size
  ) %>%
  add_markers() %>%
  layout(
    scene = list(xaxis = list(title = 'Red', color='#FF0000'),
                 yaxis = list(title = 'Green', color='#00FF00'),
                 zaxis = list(title = 'Blue', color='#0000FF'))
  )
##Add markers function adds colours to each axis in line with its name - red, green, blue
plot
problem creating directory C:\Users\dserwinowski\OneDrive - Burberry Ltd\Data Fellowship\Clustering\Clustering exercise with image\.Rproj.user\shared\notebooks\98E89FF2-Clustering exercise with image\1\42B2BA218811B71D\crjbed3sk21nx_t\lib\plotly-binding-4.7.1\lib\colourpicker: No such file or directoryover-long path lengthover-long path lengthover-long path lengthover-long path lengthover-long path length

##Plots the variable created using plot_ly

8. Fine tuning k-means

This chapter is to fine tune k-means to see how many clusters are optimal for the chosen image. For this we will use WSS (within cluster sum of squares) method.

kparameterMax <- 10
##Set the max number of clusters possible
wss <- sapply(1:kparameterMax,
        function(k){kmeans(pivotimage[c("R", "G", "B")], k)$tot.withinss})
##Calculate wss for different number of clusters for our image stored under pivotimage and store it under "wss" variable
plot(1:kparameterMax, wss,
       type="b", pch = 19, frame = FALSE,
       xlab="Number of clusters K",
       ylab="Total within-clusters sum of squares")
##This is to plot the line graph of wss variable to spot the elbow - the optimum number of clusters
abline (v=4, lty=2)

9. Recolour the image

Here we will recolour the image using centroids found only - so only 4 colours on the entire picture will be used. Each point from the image will be recoloured by the colour of its centroid depending on the cluster it’s in.

First create a new variable that will allow to store “reimaged” image by converting each point to the color of its cluster and use rgb function to convert it to HEX

kColours <- rgb(kmeansresults$centers[pivotimage$Cluster,])

Then plot it using ggplot

ggplot(data = pivotimage, aes(x = x, y = -y)) +  geom_point(colour = kColours) + coord_fixed()

10. Instagram-like filter? Why not?

So now we know how to find centroids and apply it to the image. Why not making it more Instagram-like and choose one colour and make the ret of the image greyscale? We need to choose one cluster - maybe red? So number 4.

Now we will recolour our image leaving red and turining everything else onto greyscale. However first we need to create a function that will determine it - it will be called “color_or_grey”

clusterLabel <- 4
grey_scale <- function(colour){
    grey <- colour[1] * 0.2126 + colour[2] * 0.7152 + colour[3] * 0.0722
    return(rgb(grey,grey,grey))}
## this is how the colour is converted to greyscale
color_or_grey <- function(row){
  if(row["Cluster"]==clusterLabel){
    return(rgb(row["R"],row["G"],row["B"]))
  }
  else{
    return(grey_scale(as.numeric(row[c("R","G","B")])))
  }
}
pivotimage$splash <- apply(pivotimage,1,color_or_grey)
## Then we can assign a new variable and run the apply function to check and convert it for us  

and plot it…

ggplot(data = pivotimage, aes(x = x, y = -y)) +  geom_point(colour = pivotimage$splash) + coord_fixed()

LS0tDQp0aXRsZTogIkNsdXN0ZXJpbmcgSUkiDQpvdXRwdXQ6IGh0bWxfbm90ZWJvb2sNCi0tLQ0KDQojIDEuIE92ZXJ2aWV3DQpJbiB0aGlzIG5vdGVib29rIHdlIHdpbGwgdXNlIGNsdXN0ZXJpbmcgdG8gdHJhbnNmb3JtIGEgc2FtcGxlIGltYWdlIHRvIHNlZSBob3cgY2x1c3RlcmluZyBjYW4gYmUgdXNlZCBiZXlvbmQgc2ltcGxlIGRhdGEgZnJhbWVzLg0KDQojIDIuIExpYnJhcmllcw0KQSBuZXcgbGlicmFyeSB3aWxsIGJlIGluc3RhbGxlZCBhbmQgdXNlZCAtIGltYWdlcg0KYGBge3J9DQpsaWJyYXJ5KGltYWdlcikNCmBgYA0KICANCiMgMy4gTG9hZGluZyBzYW1wbGUgaW1hZ2UNClRoaXMgZnVuY3Rpb24gd2lsbCBsb2FkIGEgc2FtcGxlIGltYWdlIGZyb20gYSBmaWxlIG9yIFVSTCB1c2luZyBpbWFnZXIgbGlicmFyeSBhbmQgc3RvcmUgaXQgYXMgQ0lNRyBmaWxlIChFZmZlY3RpdmVseSBiZWluZyBhIHZlcnkgbGFyZ2Ugc3RyaW5nIG9mIG51bWJlcnMpLg0KDQpEaXNwbGF5IGZ1bmN0aW9uIHdpbGwgc2hvdyB5b3UgdGhlIHBpY3R1cmUgaW4gdGhlIHNlcGFyYXRlIHdpbmRvdw0KDQpNb3JlIGluZm9ybWF0aW9uIGNhbiBiZSBmb3VuZCB1bmRlcjoNCmh0dHBzOi8vY3Jhbi5yLXByb2plY3Qub3JnL3dlYi9wYWNrYWdlcy9pbWFnZXIvdmlnbmV0dGVzL2dldHRpbmdzdGFydGVkLmh0bWwNCg0KYGBge3J9DQppbWFnZSA8LWxvYWQuaW1hZ2UoIkZSQUJFTC5qcGciKQ0KZGlzcGxheShpbWFnZSkNCmBgYA0KDQojIDQuIFJlZm9ybWF0dGluZyBhbiBpbWFnZQ0KSGVyZSB3ZSB3aWxsIHRyYW5zZm9ybSB0aGUgZGF0YSBmcm9tIGFuIGltYWdlIHRvIGEgZGF0YWZyYW1lIHNvIGl0IGNhbiBiZSByZWFkIGFzIGEgYnVuY2ggb2YgUkdCIChyZWQsIGdyZWVuLCBibHVlKSB2YWx1ZXMgZm9yIGEgc2luZ2xlIHBpeGVsLiBUSGlzIGlzIGFjdHVhbGx5IGhvdyBhIGNvbXB1dGVyIHN0b3JlcyBhbiBpbWFnZS4NCiAgDQoNCmBgYHtyfQ0KZGZpbWFnZSA8LSBhcy5kYXRhLmZyYW1lKGltYWdlKQ0KaGVhZChkZmltYWdlKQ0KYGBgDQogIA0KDQp4IC0gd2lkdGggIA0KeSAtIGhlaWdodCAgDQpjYyAtIGRlcHRoICANCnZhbHVlIC0gY29sb3VyIGNoYW5uZWwgIA0KICANCg0KVGhlIGZ1bmN0aW9uIGJlbG93IHJlc2hhcGUgKHRyYW5zZm9ybXMpIHRoZSBkYXRhIGZyYW1lIG9udG8gYSBwaXZvdCB0YWJsZSB0aGF0IHdpbGwgc2hvdyBSR0IgdmFsdWVzIGZvciBlYWNoIHBpeGVsIGFuZCB0dXJucyBpbnRvIGEgIndpZGUiIHBpY3R1cmUNCg0KYGBge3J9DQpwaXZvdGltYWdlIDwtIHJlc2hhcGUoZGZpbWFnZSwgZGlyZWN0aW9uID0gIndpZGUiLCB0aW1ldmFyID0gImNjIiwgaWR2YXIgPSBjKCJ4IiwgInkiKSkNCmhlYWQocGl2b3RpbWFnZSkNCmBgYA0KICANCg0KQWZ0ZXIgcmVzaGFwaW5nIC0gd2UgbmVlZCB0byByZW5hbWUgY29sdW1ucyBhcyBwZXIgdGhlIFJHQiBjb252ZW50aW9uIChhcyB0aGVzZSB2YWx1ZXMgcmVsYXRlIHRvIHRoZSBkZW5zaXR5IG9mIGVhY2ggY29sb3VyIGluIHRoZSBjb2xvdXIgbWl4KQ0KDQpgYGB7cn0NCm5hbWVzKHBpdm90aW1hZ2UpWzNdIDwtICJSIg0KbmFtZXMocGl2b3RpbWFnZSlbNF0gPC0gIkciDQpuYW1lcyhwaXZvdGltYWdlKVs1XSA8LSAiQiINCmhlYWQocGl2b3RpbWFnZSkNCg0KYGBgDQoNCiMgNS4gU25lYWsgcGVlayBvbnRvIHRoZSBpbWFnZQ0KVGhlIGVhc2llc3Qgd2F5IHRvIHNlZSB0aGUgaW1hZ2UgaXMgdG8gdXNlIGdncGxvdCBmdW5jdGlvbiBhbmQgZHJhdyBpdCBhcyBhIHBsb3QuIEZvciB0aGlzIHdlIG5lZWQgdG8gdXNlIGdncGxvdDIgbGlicmFyeQ0KICANCkhvd2V2ZXIsIGZpcnN0IHdlIG5lZWQgdG8gY29udmVydCBkYXRhIGZyb20gUkdCIHRvIEhFWCB0byBhbGxvdyBjb21wdXRlciB0byB1bmRlcnN0YW5kIHdoYXQgY29sb3VyIHRvIHVzZS4gRm9yIHRoaXMsIHdlIHdpbGwgdXNlICJyZ2IiIGZ1bmN0aW9uIGFuZCBzdG9yZSBpdCBhcyBhIHNlcGFyYXRlIHZhbHVlIHVuZGVyIGltZ2NvbG91ciB2YXJpYWJsZS4gDQoNCmBgYHtyfQ0KaW1nY29sb3VyIDwtIHJnYihwaXZvdGltYWdlW2MoIlIiLCJHIiwiQiIpXSkNCmBgYA0KICANCk5vdyB3ZSBjYW4gcGxvdCB0aGUgaW1hZ2UgdXNpbmcgZ2dwbG90IGZ1bmN0aW9uDQpgYGB7cn0NCmxpYnJhcnkoZ2dwbG90MikNCmdncGxvdChkYXRhPXBpdm90aW1hZ2UpKw0KICBhZXMoeD14LCB5PS15KSsNCiAgZ2VvbV9wb2ludChjb2xvdXI9aW1nY29sb3VyKSsNCiAgY29vcmRfZml4ZWQoKQ0KYGBgDQogIA0KX19nZ3Bsb3RfXyBmdW5jdGlvbiBhbGxvd3MgeW91IHRvIGRvIG1hbnkgdGhpbmdzLCBidXQgeW91IG5lZWQgdG8gc3BlY2lmeSBldmVyeSBwYXJhbWV0ZXIgKGFzIG9wcG9zZSB0byBxcGxvdCBmdW5jdGlvbiBmb3IgZXhhbXBsZSkuIFJlbWVtYmVyIHRvIHVzZSAiKyIgc2lnbiB0byBhZGQgYW5vdGhlciBwYXJhbWV0ZXIgIA0KX19kYXRhX18gPSBkYXRhZnJhbWUgLSBpbiB0aGlzIGNhc2UgcmVzaGFwZWQgb25lIChwaXZvdGltYWdlKSAgDQpfX2Flc19fIGFsbG93cyB0byBzcGVjaWZ5IGFlc3RoZXRpY3MgYW5kIGRpbWVuc2lvbnMuIEluIHRoaXMgY2FzZSBpdCdzIGVhc3kgKHggYW5kIHkpLCBidXQgeW91IG5lZWQgdG8gYmUgdmFyeSB0aGF0IHlvdSBuZWVkIHRvIHJldmVyc2UgeSB2YWx1ZSAoLXkpICANCl9fZ2VvbV9fIGFsbG93cyB0byBkZWZpbmUgdGhlIHNoYWUgb2YgdGhlIGdyYXBoIGFuZCBhZGQgcGFyYW1ldGVycyB0byB0aGlzIHNoYXBlLiBJbiBvdXIgY2FzZSBnZW9tX3BvaW50IGlzIGJlc3Qgc3VpdGVkIGFzIGl0IHBsb3RzIGRvdHMgd2l0aCBjb2xvcnMgZGVmaW5lZCBpbiAiY29sb3VyIiBwYXJhbWV0ZXIuIENvbG91ciBzaG91bGQgZXF1YWwgbmV3bHkgY3JlYXRlZCBIRVggdmFsdWVzIHNvIHRoYXQgdGhlIHByb2dyYW0gd2lsbCBrbm93IHdoYXQgSEVYIHZhbHVlIGVhY2ggcGl4ZWwgc2hvdWxkIGhhdmUuICAgDQpfX2Nvb3JkX2ZpeGVkX18gcGFyYW1ldGVyIGFsbG93cyB0byBmaXggdGhlIHJhdGlvIGZvciBib3RoIGF4aXMgLSBvdGhlcndpc2UgdGhlIHBpY3R1cmUgY291bGQgbG9vayB0b28gd2lkZSBvciB0b28gbmFycm93LiAgDQoNCg0KIzYuIFdvcmtpbmcgd2l0aCBrLW1lYW5zIC0gY2x1c3RlcmluZw0KSGVyZSB3ZSBhcmUgZ29pbmcgdG8gY3JlYXRlIGNsdXN0ZXJzIGZvciBvdXIgaW1hZ2UgdXNpbmcgay1tZWFucyBhbGdvcml0aG0gYW5kIGZ1bmN0aW9uLiANCg0KRmlyc3Qgd2UgbmVlZCB0byBkZWZpbmUgdGhlIG51bWJlciBvZiBjbHVzdGVycyB0aGF0IHdlIHdhbnQgdG8gaGF2ZSAtIGxldCdzIGNob29zZSAzIGFuZCBzdG9yZSBpdCB1bmRlciBhIG5ldyB2YXJpYWJsZQ0KDQpgYGB7cn0NCmtwYXJhbWV0ZXIgPC0gNA0KYGBgDQogIA0KVGhlbiB3ZSBuZWVkIHRvIGRlZmluZSBpbWdDbHVzdGVyIHZhcmlhYmxlIHRoYXQgd2lsbCBzdG9yZSBhbGwgcm93cyBmcm9tIHRoZSBwaXZvdCB0YWJsZSBidXQgb25seSBSR0IgY29sdW1ucw0KYGBge3J9DQppbWdDbHVzdGVyIDwtIGRhdGEuZnJhbWUocGl2b3RpbWFnZSRSLCBwaXZvdGltYWdlJEcsIHBpdm90aW1hZ2UkQikNCmhlYWQoaW1nQ2x1c3RlcikNCmBgYA0KDQpOb3cgd2UncmUgZ29pbmcgdG8gdXNlIGstbWVhbnMgdG8gZmluZCBjZW50cm9pZHMgZm9yIHVzLiBUaGVzZSBhcmUgc2hvd24gYmVsb3cgYW5kIHJlcHJlc2VudHMgbW9zdCBpbXBvcnRhbnQgY29sb3VycyBvbiB0aGUgaW1hZ2UNCmBgYHtyfQ0Ka21lYW5zcmVzdWx0cyA8LSBrbWVhbnMoaW1nQ2x1c3RlciwgY2VudGVycyA9IGtwYXJhbWV0ZXIpDQprbWVhbnNyZXN1bHRzJGNlbnRlcnMNCmBgYA0KICANCkstbWVhbnMgYWxzbyBjcmVhdGVkIGNsdXN0ZXJzIGZvciBlYWNoIHBpeGVsIHNvIHdlIGNhbiBncm91cCBwaXhlbHMgdG9nZXRoZXIuIE5vdyBhZGRpbmcgbmV3bHkgY3JlYXRlZCBncm91cHMgdG8gZWFjaCBwaXhlbA0KYGBge3J9DQpwaXZvdGltYWdlJENsdXN0ZXIgPC0ga21lYW5zcmVzdWx0cyRjbHVzdGVyDQpgYGANCg0KIzcuIENsdXN0ZXIgdmlzdWFsaXNhdGlvbg0KVGhpcyBpcyBob3cgeW91IGNhbiB2aXN1YWxpemUgdGhlIHJlc3VsdHMgb2YgdGhlIGNsdXN0ZXJpbmcuIFRvIGRvIHRoYXQgd2Ugd2lsbCB1c2Ugc29tZSBmdW5jdGlvbnMgZnJvbSAicGxvdGx5IiBsaWJyYXJ5IHNvIHlvdSdkIG5lZWQgdG8gaW5zdGFsbCBpdCBmaXJzdC4NCiAgDQpGaXJzdCB3ZSBuZWVkIHRvIGNvbnZlcnQgY2VudHJvaWRzIGZvdW5kIGZyb20gUkdCIG9udG8gSEVYIHVzaW5nIHJnYiBmdW5jdGlvbi4NCmBgYHtyfQ0KQ2x1c3RlckNvbG91cnMgPC0gcmdiKGttZWFuc3Jlc3VsdHMkY2VudGVycykNCkNsdXN0ZXJDb2xvdXJzDQpgYGANCiAgDQpOb3cgd2UgaGF2ZSBnb3QgY29sb3VycyBvZiB0aGVzZSBjZW50cm9pZHMgYW5kIHdlIGNhbiB1c2UgcGxvdCBmdW5jdGlvbiB0byB2aWV3IHRoZW0uIFRoaXMgY29kZSBibG9jayB3aWxsIHBsb3QgcmVjdGFuZ3VsYXIgYm94ZXMgaW4gZWFjaCBjb2xvciAoY2VudHJvaWQpIHdpdGggYSBuYW1lIG9mIHRoZSBjbHVzdGVyIGluIGl0LiANCg0KYGBge3J9DQpTZXRUZXh0Q29udHJhc3RDb2xvciA8LSBmdW5jdGlvbihjb2xvcikNCnsNCiAgaWZlbHNlKCBtZWFuKGNvbDJyZ2IoY29sb3IpKSA+IDEyNywgImJsYWNrIiwgIndoaXRlIil9DQojI0Z1bmN0aW9uIGFib3ZlIHdpbGwgYWxsb3cgeW91IHRvIGRlZmluZSB3aGV0aGVyIHRvIHNldCB0aGUgY29sb3Igb2YgdGhlIGNsdXN0ZXIgbmFtZSBpbiB3aGl0ZSBvciBibGFjayBkZXBlbmRpbmcgb24gdGhlIGNsdXN0ZXIgY29sb3VyIChpZiBkYXJrIHRoZW4gd2hpdGUgbGFiZWwgYW5kIHZpY2UgdmVyc2EpDQoNCg0KcGxvdCgwLCB0eXBlID0gIm4iLCBheGVzID0gRkFMU0UsIHlsYWIgPSAiIiwgeGxhYiA9ICIiLCB5bGltID0gYygyLDApLCB4bGltID0gYygwLDUpKQ0KdGl0bGUoIkNsdXN0ZXJzIGFzIGNvbG91cnMiKQ0KIyNQbG90dGluZyBhIHNwYWNlIHdpdGhvdXQgZGF0YSAoMCksIHR5cGUgbiwgYXhlcyBub3QgdmlzaWJsZSBhbmQgd2l0aCBzaXplIDUgaW4gd2lkdGggYW5kIHNpemUgMiBoZWlnaHQNCg0KZm9yIChpIGluIDA6KGtwYXJhbWV0ZXItMSkpIHsNCiAgcmVjdChpLDAsaSsxLDEsY29sPUNsdXN0ZXJDb2xvdXJzW2krMV0pDQogIHRleHQoaSswLjUsMC41LCBpKzEsIGNvbD1TZXRUZXh0Q29udHJhc3RDb2xvcihDbHVzdGVyQ29sb3Vyc1tpKzFdKSl9DQojI1RoaXMgbG9vcCBmdW5jdGlvbiB3aWxsIHBsb3QgcmVjdGFuZ3VsYXJzIGluIGNvbG9ycyBvZiBjbHVzdGVycyBhbmQgbGFiZWxzIG9uIHRoZSBwcmV2aW91c2x5IGNyZWF0ZWQgc3BhY2UuIA0KDQpgYGANCg0KTm93IHdlJ3JlIGFkZGluZyBjbHVzdGVyIGdyb3VwIHRvIGVhY2ggcG9pbnQgaW4gdGhlIGltZ0NsdXN0ZXIgZnJhbWUgYmFzZWQgb24gY2VudHJvaWRzIGZvdW5kIHVzaW5nIGstbWVhbnMNCmBgYHtyfQ0KaW1nQ2x1c3RlciRjbHVzdGVyIDwta21lYW5zcmVzdWx0cyRjbHVzdGVyDQpoZWFkKGltZ0NsdXN0ZXIpDQpgYGANCg0KTm93IHdlJ3JlIHJlYWR5IHRvIHBsb3Qgc29tZSBtb3JlIC4uDQoNCg0KYGBge3J9DQpsaWJyYXJ5KHBsb3RseSkNCmltZ1Bpdm90U2FtcGxlIDwtIHBpdm90aW1hZ2Vbc2FtcGxlKDE6bnJvdyhwaXZvdGltYWdlKSwgMTAwMCwgcmVwbGFjZT1GQUxTRSksXQ0KIyNDcmVhdGluZyBhIHNhbXBsZSBvZiBwb2ludHMgZnJvbSB0aGUgaW1hZ2UgKHByb2Nlc3Npbmcgb2YgdGhlIGZ1bGwgaW1hZ2UgbWlnaHQgY3Jhc2ggY29tcHV0ZXIgYXMgaXQgaGFzIG1pbGxpb25zIG9mIHBpeGVscykNCg0KcGxvdCA8LSBwbG90X2x5KA0KICAgIGltZ1Bpdm90U2FtcGxlLCB4ID0gflIsIHkgPSB+RywgeiA9IH5CLA0KIyNUYWtlIHNhbXBsZSBvZiAxMDAwIHBvaW50cyBhbmQgZm9yIGVhY2ggcG9pbnQgLSBpbWdQaXZvdFNhbXBsZQ0KIyMgRm9yIGVhY2ggZGltZW5zaW9uIHgseSx6IGFzc2lnbiBvbmUgY29sb3VyIChSLEcsQikgc28gUkdCIHdvdWxkIGJlIGNvb3JkaW5hdGVzIG9uIHRoZSAzRCBwbG90DQogICAgY29sb3IgPSB+Q2x1c3RlciwgDQojIyBDb2xvciBwYXJhbWV0ZXIgdGFrZXMgdGhlIHZhbHVlIGZyb20gdGhlIGNsdXN0ZXIgY29sdW1uIGZvciBlYWNoIHBvaW50IGFuZCBwbG90IHRoaXMgcG9pbnQgaW4gYSBjb2xvdXIgb2YgdGhlIGNsdXN0ZXIgDQogICAgY29sb3JzID0gcmdiKGttZWFuc3Jlc3VsdHMkY2VudGVycyksDQojIyBjb2xvcnMgcGFyYW1ldGVyIHNob3dzIGEgdmVjdG9yIG9mIGNvbG91cnMgaW4gSEVYIGZvcm1hdCAoYWZ0ZXIgY29udmVydGluZyBjZW50cm9pZHMgdXNpbmcgcmdiIGZ1bmN0aW9uKQ0KICAgIG1hcmtlciA9IGxpc3Qoc3ltYm9sID0gImNpcmNsZSIsIHNpemUgPSA0KQ0KIyMgbWFya2VyIHBhcmFtZXRlciBzZXRzIHBvaW50IHR5cGUgYW5kIHNpemUNCiAgKSAlPiUNCiAgYWRkX21hcmtlcnMoKSAlPiUNCiAgbGF5b3V0KA0KICAgIHNjZW5lID0gbGlzdCh4YXhpcyA9IGxpc3QodGl0bGUgPSAnUmVkJywgY29sb3I9JyNGRjAwMDAnKSwNCiAgICAgICAgICAgICAgICAgeWF4aXMgPSBsaXN0KHRpdGxlID0gJ0dyZWVuJywgY29sb3I9JyMwMEZGMDAnKSwNCiAgICAgICAgICAgICAgICAgemF4aXMgPSBsaXN0KHRpdGxlID0gJ0JsdWUnLCBjb2xvcj0nIzAwMDBGRicpKQ0KICApDQojI0FkZCBtYXJrZXJzIGZ1bmN0aW9uIGFkZHMgY29sb3VycyB0byBlYWNoIGF4aXMgaW4gbGluZSB3aXRoIGl0cyBuYW1lIC0gcmVkLCBncmVlbiwgYmx1ZQ0KDQpwbG90DQojI1Bsb3RzIHRoZSB2YXJpYWJsZSBjcmVhdGVkIHVzaW5nIHBsb3RfbHkNCg0KYGBgDQoNCiM4LiBGaW5lIHR1bmluZyBrLW1lYW5zDQpUaGlzIGNoYXB0ZXIgaXMgdG8gZmluZSB0dW5lIGstbWVhbnMgdG8gc2VlIGhvdyBtYW55IGNsdXN0ZXJzIGFyZSBvcHRpbWFsIGZvciB0aGUgY2hvc2VuIGltYWdlLiBGb3IgdGhpcyB3ZSB3aWxsIHVzZSBXU1MgKHdpdGhpbiBjbHVzdGVyIHN1bSBvZiBzcXVhcmVzKSBtZXRob2QuIA0KDQoNCmBgYHtyfQ0Ka3BhcmFtZXRlck1heCA8LSAxMA0KIyNTZXQgdGhlIG1heCBudW1iZXIgb2YgY2x1c3RlcnMgcG9zc2libGUNCg0Kd3NzIDwtIHNhcHBseSgxOmtwYXJhbWV0ZXJNYXgsDQogICAgICAgIGZ1bmN0aW9uKGspe2ttZWFucyhwaXZvdGltYWdlW2MoIlIiLCAiRyIsICJCIildLCBrKSR0b3Qud2l0aGluc3N9KQ0KIyNDYWxjdWxhdGUgd3NzIGZvciBkaWZmZXJlbnQgbnVtYmVyIG9mIGNsdXN0ZXJzIGZvciBvdXIgaW1hZ2Ugc3RvcmVkIHVuZGVyIHBpdm90aW1hZ2UgYW5kIHN0b3JlIGl0IHVuZGVyICJ3c3MiIHZhcmlhYmxlDQoNCnBsb3QoMTprcGFyYW1ldGVyTWF4LCB3c3MsDQogICAgICAgdHlwZT0iYiIsIHBjaCA9IDE5LCBmcmFtZSA9IEZBTFNFLA0KICAgICAgIHhsYWI9Ik51bWJlciBvZiBjbHVzdGVycyBLIiwNCiAgICAgICB5bGFiPSJUb3RhbCB3aXRoaW4tY2x1c3RlcnMgc3VtIG9mIHNxdWFyZXMiKQ0KIyNUaGlzIGlzIHRvIHBsb3QgdGhlIGxpbmUgZ3JhcGggb2Ygd3NzIHZhcmlhYmxlIHRvIHNwb3QgdGhlIGVsYm93IC0gdGhlIG9wdGltdW0gbnVtYmVyIG9mIGNsdXN0ZXJzDQoNCmFibGluZSAodj00LCBsdHk9MikNCmBgYA0KDQoNCiM5LiBSZWNvbG91ciB0aGUgaW1hZ2UNCkhlcmUgd2Ugd2lsbCByZWNvbG91ciB0aGUgaW1hZ2UgdXNpbmcgY2VudHJvaWRzIGZvdW5kIG9ubHkgLSBzbyBvbmx5IDQgY29sb3VycyBvbiB0aGUgZW50aXJlIHBpY3R1cmUgd2lsbCBiZSB1c2VkLiBFYWNoIHBvaW50IGZyb20gdGhlIGltYWdlIHdpbGwgYmUgcmVjb2xvdXJlZCBieSB0aGUgY29sb3VyIG9mIGl0cyBjZW50cm9pZCBkZXBlbmRpbmcgb24gdGhlIGNsdXN0ZXIgaXQncyBpbi4NCiAgDQpGaXJzdCBjcmVhdGUgYSBuZXcgdmFyaWFibGUgdGhhdCB3aWxsIGFsbG93IHRvIHN0b3JlICJyZWltYWdlZCIgaW1hZ2UgYnkgY29udmVydGluZyBlYWNoIHBvaW50IHRvIHRoZSBjb2xvciBvZiBpdHMgY2x1c3RlciBhbmQgdXNlIHJnYiBmdW5jdGlvbiB0byBjb252ZXJ0IGl0IHRvIEhFWA0KYGBge3J9DQprQ29sb3VycyA8LSByZ2Ioa21lYW5zcmVzdWx0cyRjZW50ZXJzW3Bpdm90aW1hZ2UkQ2x1c3RlcixdKQ0KYGBgDQogIA0KVGhlbiBwbG90IGl0IHVzaW5nIGdncGxvdA0KYGBge3J9DQpnZ3Bsb3QoZGF0YSA9IHBpdm90aW1hZ2UsIGFlcyh4ID0geCwgeSA9IC15KSkgKyAgZ2VvbV9wb2ludChjb2xvdXIgPSBrQ29sb3VycykgKyBjb29yZF9maXhlZCgpDQpgYGANCg0KIzEwLiBJbnN0YWdyYW0tbGlrZSBmaWx0ZXI/IFdoeSBub3Q/DQpTbyBub3cgd2Uga25vdyBob3cgdG8gZmluZCBjZW50cm9pZHMgYW5kIGFwcGx5IGl0IHRvIHRoZSBpbWFnZS4gV2h5IG5vdCBtYWtpbmcgaXQgbW9yZSBJbnN0YWdyYW0tbGlrZSBhbmQgY2hvb3NlIG9uZSBjb2xvdXIgYW5kIG1ha2UgdGhlIHJldCBvZiB0aGUgaW1hZ2UgZ3JleXNjYWxlPw0KV2UgbmVlZCAgdG8gY2hvb3NlIG9uZSBjbHVzdGVyIC0gbWF5YmUgcmVkPyBTbyBudW1iZXIgNC4NCg0KTm93IHdlIHdpbGwgcmVjb2xvdXIgb3VyIGltYWdlIGxlYXZpbmcgcmVkIGFuZCB0dXJpbmluZyBldmVyeXRoaW5nIGVsc2Ugb250byBncmV5c2NhbGUuIEhvd2V2ZXIgZmlyc3Qgd2UgbmVlZCB0byBjcmVhdGUgYSBmdW5jdGlvbiB0aGF0IHdpbGwgZGV0ZXJtaW5lIGl0IC0gaXQgd2lsbCBiZSBjYWxsZWQgImNvbG9yX29yX2dyZXkiDQogIA0KYGBge3J9DQpjbHVzdGVyTGFiZWwgPC0gNA0KZ3JleV9zY2FsZSA8LSBmdW5jdGlvbihjb2xvdXIpew0KICAgIGdyZXkgPC0gY29sb3VyWzFdICogMC4yMTI2ICsgY29sb3VyWzJdICogMC43MTUyICsgY29sb3VyWzNdICogMC4wNzIyDQogICAgcmV0dXJuKHJnYihncmV5LGdyZXksZ3JleSkpfQ0KIyMgdGhpcyBpcyBob3cgdGhlIGNvbG91ciBpcyBjb252ZXJ0ZWQgdG8gZ3JleXNjYWxlDQoNCmNvbG9yX29yX2dyZXkgPC0gZnVuY3Rpb24ocm93KXsNCiAgaWYocm93WyJDbHVzdGVyIl09PWNsdXN0ZXJMYWJlbCl7DQogICAgcmV0dXJuKHJnYihyb3dbIlIiXSxyb3dbIkciXSxyb3dbIkIiXSkpDQogIH0NCiAgZWxzZXsNCiAgICByZXR1cm4oZ3JleV9zY2FsZShhcy5udW1lcmljKHJvd1tjKCJSIiwiRyIsIkIiKV0pKSkNCiAgfQ0KfQ0KDQpwaXZvdGltYWdlJHNwbGFzaCA8LSBhcHBseShwaXZvdGltYWdlLDEsY29sb3Jfb3JfZ3JleSkNCiMjIFRoZW4gd2UgY2FuIGFzc2lnbiBhIG5ldyB2YXJpYWJsZSBhbmQgcnVuIHRoZSBhcHBseSBmdW5jdGlvbiB0byBjaGVjayBhbmQgY29udmVydCBpdCBmb3IgdXMgIA0KYGBgDQogIA0KYW5kIHBsb3QgaXQuLi4NCmBgYHtyfQ0KZ2dwbG90KGRhdGEgPSBwaXZvdGltYWdlLCBhZXMoeCA9IHgsIHkgPSAteSkpICsgIGdlb21fcG9pbnQoY29sb3VyID0gcGl2b3RpbWFnZSRzcGxhc2gpICsgY29vcmRfZml4ZWQoKQ0KYGBgDQoNCg==